Vés al contingut

Diagrama de Hasse

De la Viquipèdia, l'enciclopèdia lliure
Elements de P (P (P (P ({})))) en Diagrama de Hasse.

En matemàtiques, un diagrama de Hasse és una representació gràfica simplificada d'un conjunt parcialment ordenat finit. Això s'aconsegueix eliminant informació redundant. Per a això es dibuixa una aresta ascendent entre dos elements només si un segueix a un altre sense haver altres elements intermedis.

En un diagrama de Hasse s'elimina la necessitat de representar:

  • Cicles d'un element, ja que s'entén que una relació d'ordre parcial és reflexiva.
  • Arestes que es dedueixen de la transitivitat de la relació.

Definició

[modifica]
  • De dos membres x i y d'un conjunt parcialment ordenat S que « y segueix x » si x y i no hi ha element de S entre x i y.

L'ordre parcial és llavors precisament la clausura transitiva de la relació de seguir .

  • El diagrama de Hasse de S es defineix com el conjunt de tots els parells ordenats ( x , y ) tals que y segueix x , és a dir, el diagrama de Hasse es pot identificar amb la relació de seguir .

Exemple

[modifica]

Concretament, es representa cada membre de S com un punt negre a la pàgina i es dibuixa una línia que vagi cap amunt de x a y si y segueix x.

Per exemple, sigui el conjunt A ={1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}(tots els divisors de 60). Aquest conjunt està ordenat parcialment per la relació de divisibilitat. El seu diagrama de Hasse pot ser representat de la manera següent:

Diagrama de Hasse
Diagrama de Hasse

Per exemple, en el diagrama de Hasse del Poset de tots els divisors d'un nombre n , ordenats parcialment per divisibilitat, n mateix està en el límit del diagrama, el número 1 estaria en el fons, i els divisors més petits (cosins) seguirien l'element inferior.

Relació amb els grafs

[modifica]

Un diagrama de Hasse es pot veure també com un graf al qual se li lleven tots els seus bucles i els seus arestes que poden deduir amb la propietat transitiva i propietat reflexiva.

La dificultat de trobar un bon diagrama de Hasse

[modifica]

Les relacions «seguir» queda definida de manera única a partir de la relació d'ordre inicial. Això fa que les arestes del diagrama de Hasse i els punts que connecten quedin determinats també de forma única. Però hi ha un problema addicional: trobar una ubicació adequada per als vèrtexs que pugui reflectir alguna de les simetries subjacents. En aquest sentit, trobar un bon diagrama és difícil.

S'han proposat diversos algorismes per a dibuix de «bons» diagrames, però avui dia la seva construcció segueix basant-se en una forta intervenció humana. De fet, fins i tot un humà necessita bastant pràctica per elaborar-los.

Els següents exemples corresponen a diagrames de Hasse d'una mateixa relació d'ordre:

Hipercub 4-D, segons la distància des d'una cantonada Projecció de l'hipercub 4-D Projecció per arestes de l'hipercub

Nota

[modifica]